package com.example.algorithm.sort;

// 学习顺序：第二
// 用第i个元素比较后面的所有元素，从前往后比较，一直找到最小的一个挪到最左边，其实就是替换i的位置，与冒泡排序相反。
// 第一次能找到最小的元素，第二次能找到第二小的元素。。。。复杂度：n^2
public class SelectionSort {
    public static void main(String[] args) {
        int[] array = {5, 3, 8, 4, 2};

        System.out.println("排序前的数组：");
        printArray(array);

        selectionSort(array);

        System.out.println("\n排序后的数组：");
        printArray(array);
    }

    // 选择排序方法
    // 这个过程确实是有点绕的。不过我觉得想清楚一次之后，没必要说靠画图来记住它的流程。就直接多写几遍代码来记住代码就好。反正面试的时候是直接上代码的。简单粗暴直接才是最有效的。
    public static void selectionSort(int[] array) {
        int n = array.length;
        // 选择排序，整个过程都是找小的哦。
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                // i的取值集合只有[0,1,2,3], array[minIndex]分别是array[0]、array[1]、array[2]、array[3]。这是一个细节。i控制的是j的起点，所以，i控制到倒数第二个就好，也就是i的最大值是3
                // array[j]对应上面4个array[i]分别是
                // array[0]: array[1]、array[2]、array[3]、array[4]
                // array[1]: array[2]、array[3]、array[4]
                // array[2]: array[3]、array[4]
                // array[3]: array[4]
                if (array[j] < array[minIndex]) {
                    minIndex = j; // 某一轮的i内，与不同的j打擂。minIndex用来承载打擂打出来的那个最小的，可以看做是一个临时变量。
                }
            }
            // 然后在某一轮的i内，将新的最小的擂主，与当前轮的array[i]交换位置。
            int temp = array[minIndex]; // 先取出array[j]
            array[minIndex] = array[i]; // 然后把array[i]赋值给array[j]
            array[i] = temp; // 把array[j]赋值给array[i]
        }
    }

    // 打印数组方法
    public static void printArray(int[] array) {
        for (int num : array) {
            System.out.print(num + " ");
        }
    }
}

// 后记
// (重要)在学习完了冒泡排序、选择排序之后，我来总结一下。个人认为这些总结比较重要：
// 起初我以为，冒泡排序、选择排序的思维是一样的，只是遍历的方向是相反的而已。
// 但是，事实上，不是这样的。冒泡排序，是没有一个专门用来存放最大值对应的索引的临时变量的，所以，在内层循环里面，它每次比较大小完之后如果需要交换，那就直接当场相邻的两个元素交换。
// 但是，选择排序的交换次数，没有，它是引入了一个专门存放最值(最小值)的临时变量的。它不会在第二层循环里面做频繁的相邻元素的交换。它会在第一层循环那里，一次性把最值元素与无序区最左边的那个元素交换。
// 事实上，这种写法也可以在冒泡排序里面使用。但是，我猜，冒泡排序可能就是相邻的这样交换。而选择排序，可能就是确定了最值之后一次交换搞定。

